題目

題目翻譯

檢查一串括號是否為合法括號，而合法括號的要件是要左括號等於右括號的數量，並且要兩兩成對，且相同類型的括號要配相同類型的括號（譬如大括號要配大括號）。如果是合法括號就回傳true，否則回傳false。

解題思路

1. 問題描述：

   • 給定一個只包含 (、)、{、}、[ 和 ] 的字符串，判斷這個字符串中的括號是否配對正確並且順序正確。有效的括號必須滿足：
     • 左括號必須用相同類型的右括號閉合。
     • 左括號必須以正確的順序閉合。

2. 思路分析：

   • 使用一個堆疊來處理括號匹配問題。
   • 當遍歷到一個左括號（(、[、{），將其推入堆疊中。
   • 當遇到右括號時，檢查堆疊頂部是否有對應的左括號，如果有則彈出堆疊頂部元素；如果沒有或者堆疊為空，則匹配失敗。
   • 最後檢查堆疊是否為空，為空則表示括號全部匹配成功，否則匹配失敗。

3. 步驟分解：

   • 步驟1：初始化一個空的堆疊，用於存儲左括號。
   • 步驟2：遍歷字符串中的每個字符。
     • 如果是左括號，將其加入堆疊。
     • 如果是右括號，檢查堆疊是否為空或者堆疊頂部的左括號是否與當前右括號匹配。
   • 步驟3：在遍歷完成後，檢查堆疊是否為空，為空則表示括號匹配正確。
   • 步驟4：返回結果。

改寫後的程式碼

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;  // 使用堆疊來匹配括號
        
        // 遍歷字符串中的每個字符
        for (char c : s) {
            // 如果是左括號，推入堆疊
            if (c == '(' || c == '{' || c == '[') {
                st.push(c);
            }
            // 如果是右括號，進行匹配
            else {
                // 堆疊為空，或者堆疊頂部不匹配，直接返回false
                if (st.empty()) return false;
                
                char top = st.top();
                if ((c == ')' && top == '(') || 
                    (c == ']' && top == '[') || 
                    (c == '}' && top == '{')) {
                    st.pop();  // 匹配成功，彈出堆疊頂部
                } else {
                    return false;  // 匹配失敗
                }
            }
        }
        
        // 最後檢查堆疊是否為空
        return st.empty();
    }
};